/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.google.code.peersim.pastry.protocol;

import com.google.code.peersim.metrics.ProximityMetricIfc;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

/**
 * A Pastry neighborhood-set is a set of {@code M} {@link PastryNodeDescriptor}s
 * each of them pointing to a node that is amongst the closest ones (according to the applied proximity
 * metric) to the node owning the current neighborhood-set.<br>
 * The {@code M} parameter is provided by {@link PastryProtocol#getM()}.
 *
 * @author frusso
 * @version 0.1
 * @since 0.1
 */
class PastryNeighborhoodSet implements Iterable<PastryNodeDescriptor> {

  /**
   * The node owning this neighborhood-set.
   */
  private final PastryNodeDescriptor owner;
  /**
   * The proximity metric used to evaluate the distance between node-pairs.
   */
  private final ProximityMetricIfc metric;
  /**
   * Pastry's M configuration parameter.
   */
  private final int m;
  /**
   * The actual neighborhood-set.
   */
  private final NavigableSet<Entry> neighborhood;

  /**
   * Factory method for instantiating new {@link PastryNeighborhoodSet}s for actual runtime use.
   *
   * @param m Pastry's M configuration parameter
   * @param owner The owner of this {@link PastryNeighborhoodSet}
   * @param metric The {@link ProximityMetricIfc} implementation that must be used to compute distances
   * @return An empty {@link PastryNeighborhoodSet}
   */
  static PastryNeighborhoodSet newInstance(int m, PastryNodeDescriptor owner, ProximityMetricIfc metric) {
    return new PastryNeighborhoodSet(m, owner, metric);
  }

  /**
   * Constructor. Requires:
   * <ol>
   * <li>the metadata about the node owning the current neighborhood-set</li>
   * <li>a valid {@link ProximityMetricIfc} implementation that will be used for measuring the distance between pairs of nodes</li>
   * </ol>
   *
   * @param m The maximum number of allowed entries
   * @param owner The owner
   * @param metric The metric
   * @param forTest If we are testing or not
   * @param r The source of randomness
   */
  private PastryNeighborhoodSet(int m, PastryNodeDescriptor owner, ProximityMetricIfc metric) {
    this.m = m;
    this.owner = owner;
    this.metric = metric;
    neighborhood = new TreeSet<Entry>();
  }

  /**
   * Adds the given node to the neighborhood iff either:
   * <ol>
   * <li>the neighborhood-set has not reached yet its maximum size {@link PastryProtocol#getM()}</li>
   * <li>the neighborhood-set has already not reached its maximum size {@link PastryProtocol#getM()}
   * but the distance between {@link PastryNeighborhoodSet#owner} and {@code neighbor} is less than
   * the one of the farthest node currently stored in the neighborhood, according to the configured
   * metric</li>
   * </ol>
   * <b>Note:</b> if the candidate node was as far as the currently farthest one, the former would not
   * be added to the neighborhood to prevent resource consumption.
   *
   * @param neighbor The candidate neighbor
   * @return {@link Boolean#TRUE} iff {@code neighbor} has been added, {@link Boolean#FALSE} otherwise
   */
  final boolean addNeighbor(PastryNodeDescriptor candidate) {
    boolean added = false;
    if(!this.owner.equals(candidate)) {
      if (m != 0) { // check just to avoid NoSuchElementException while working with the inner Set
        double d = metric.unsignedDistanceBetween(owner, candidate);
        if (neighborhood.size() == m) {
          Entry farthest = neighborhood.last();
          if (d < farthest.distance) {
            _addNeighbor(candidate, d);
            neighborhood.remove(farthest);
          }
        } else {
          _addNeighbor(candidate, d);
        }
      }
    }
    return added;
  }

  /**
   * Tells whether the provided node is stored in this set or not.
   *
   * @param node The node to look for
   * @return Whether the provided node is stored in this set or not
   */
  final boolean contains(PastryNode node) {
    boolean found = false;
    for(Entry entry : neighborhood) {
      if(entry.getNode().getPastryId().equals(node.getPastryId())) {
        found = true;
        break;
      }
    }
    return found;
  }

  /**
   * This method empties the whole neighborhood-set bringing its size to zero.
   */
  final void empty() {
    neighborhood.clear();
  }

  /**
   * Returns an unmodifieble view of all the neighbors.
   *
   * @return An unmodifieble view of all the neighbors
   */
  final List<PastryNode> getAllNeighbors() {
    List<PastryNode> list = new ArrayList<PastryNode>();
    for(PastryNodeDescriptor pnd : this) {
      list.add(pnd.getPastryNode());
    }
    return Collections.unmodifiableList(list);
  }

  /**
   * Returns the closest node in the neighborhood-set, or {@code null} if the set
   * was empty.
   *
   * @return The closest node in the neighborhood-set, or {@code null} if the set
   * was empty
   */
  final PastryNodeDescriptor getClosest() {
    PastryNodeDescriptor closest = null;
    if (!neighborhood.isEmpty()) {
      closest = neighborhood.first().getNode();
    }
    return closest;
  }

  /**
   * Returns the farthest node in the neighborhood-set, or {@code null} if the set
   * was empty.
   *
   * @return The farthest node in the neighborhood-set, or {@code null} if the set
   * was empty
   */
  final PastryNodeDescriptor getFarthest() {
    PastryNodeDescriptor farthest = null;
    if (!neighborhood.isEmpty()) {
      farthest = neighborhood.last().getNode();
    }
    return farthest;
  }

  /**
   * Returns Pastry's {@link PastryProtocol#getM()} configuration parameter.
   *
   * @return Pastry's M configuration parameter
   */
  final int getM() {
    return m;
  }

  /**
   * Returns {@link Boolean#TRUE} if {@link PastryNeighborhoodSet#size()} is zero,
   * {@link Boolean#FALSE} otherwise.
   *
   * @return {@link Boolean#TRUE} if {@link PastryNeighborhoodSet#size()} is zero,
   * {@link Boolean#FALSE} otherwise
   */
  final boolean isEmpty() {
    return this.neighborhood.isEmpty();
  }

  /**
   * Given the {@link PastryNeighborhoodSet} called {@code that}, this method merges its
   * content with the one currently held. The merging process applies the very same logic
   * as defined by the {@link PastryNeighborhoodSet#addNeighbor(com.google.code.peersim.pastry.protocol.PastryNodeDescriptor)}
   * method for each {@link PastryNodeDescriptor} stored inside {@code that}.
   * Should {@code that} be empty or {@code null}, this method would simply do nothing.
   *
   * @param that The neighborhood set to use to enrich the current one
   * @return This (enriched) neighborhood set
   */
  final PastryNeighborhoodSet merge(PastryNeighborhoodSet that) {
    if (that != null && !that.isEmpty()) {
      for (PastryNodeDescriptor node : that) {
        this.addNeighbor(node);
      }
    }
    return this;
  }

  /**
   * Removes the given node from the set.
   *
   * @param node The node to be removed
   */
  final void remove(PastryNode node) {
    Iterator<Entry> iter = neighborhood.iterator();
    while(iter.hasNext()) {
      Entry entry = iter.next();
      if(entry.getNode().getPastryId().equals(node.getPastryId())) {
        iter.remove();
        break;
      }
    }
  }

  /**
   * Returns the number of entries currently stored.
   *
   * @return The number of entries currently stored
   */
  final int size() {
    return this.neighborhood.size();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public final String toString() {
    StringBuilder ns = new StringBuilder();
    for(Entry entry : neighborhood) {
      ns.append(entry).append("\n");
    }
    return "PROPERTIES [M: " + m + ", owner: " + owner + ", metric: " + metric + "]\n" + ns.toString();
  }

  /**
   * Iterates over the at most {@link PastryProtocol#getM()} {@link PastryNodeDescriptor}s
   * stored in the neighborhood-set in ascending order, that is from the closest one to
   * the last.
   *
   * {@inheritDoc}
   * @return
   */
  public final Iterator<PastryNodeDescriptor> iterator() {
    return new Iterator<PastryNodeDescriptor>() {

      private Iterator<Entry> iter = neighborhood.iterator();

      public boolean hasNext() {
        return iter.hasNext();
      }

      public PastryNodeDescriptor next() {
        return iter.next().getNode();
      }

      public void remove() {
        throw new IllegalStateException("Opertaion not permitted.");
      }
    };
  }

  /**
   * Internal method used to perform a {@link PastryNodeDescriptor} addition to
   * the internal set. This method does not perform any check aimed at verifying
   * whether {@code candidate} can be added or not, thus its direct and uncontrolled
   * use might lead to wrong results and inconsistent states.
   *
   * @param candidate The new neighbor that must be added
   * @param d The new neighbor's distance from the owner
   * @return {@link Boolean#TRUE} iff the add succeeds, {@link Boolean#FALSE} otherwise
   */
  private boolean _addNeighbor(PastryNodeDescriptor candidate, double d) {
    Entry newNeighbor = new Entry(candidate, d);
    return neighborhood.add(newNeighbor);
  }

  /**
   * Mutable class conceived to represent {@link PastryNeighborhoodSet} entries stored
   * into {@link PastryNeighborhoodSet}'s internal data-structures. This class is {@code private}
   * since it is not meant to be used externally.<br>
   * The {@link ProximityMetricIfc.MeasurableEntity} interface must be implemented in order to use
   * {@link Entry} instances as argument for calls to
   * {@link ProximityMetricIfc#unsignedDistanceBetween(come.google.code.peersim.metrics.ProximityMetricIfc.MeasurableEntity, come.google.code.peersim.metrics.ProximityMetricIfc.MeasurableEntity)}.
   * 
   * @author frusso
   * @version 0.1
   * @since 0.1
   */
  private static class Entry implements Comparable<Entry> {

    /**
     * The node the entry refers to.
     */
    private PastryNodeDescriptor node;
    /**
     * The distance from the {@link PastryNeighborhoodSet#owner}.
     */
    private double distance;

    /**
     * Constructor.
     *
     * @param n The node
     * @param d The distance
     * @param forTest
     * @param r
     */
    private Entry(PastryNodeDescriptor n, double d) {
      node = n;
      distance = d;
    }

    /**
     * Parameterless constructor.
     */
    private Entry() {
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int compareTo(Entry e) {
      return Double.valueOf(this.distance).compareTo(Double.valueOf(e.distance));
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean equals(Object other) {
      if(!(other instanceof Entry))
        return false;
      return node.equals(((Entry)other).node) && distance == ((Entry)other).distance;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int hashCode() {
      int hash = 7;
      hash = 53 * hash + (this.node != null ? this.node.hashCode() : 0);
      hash = 53 * hash + (int) (Double.doubleToLongBits(this.distance) ^ (Double.doubleToLongBits(this.distance) >>> 32));
      return hash;
    }

    /**
     * Returns the distance from the {@link PastryNeighborhoodSet#owner}.
     *
     * @return The distance form the {@link PastryNeighborhoodSet#owner}
     */
    double getDistance() {
      return distance;
    }

    /**
     * Returns a reference to the node.
     *
     * @return The node
     */
    PastryNodeDescriptor getNode() {
      return node;
    }

    /**
     * Sets the {@link PastryNodeDescriptor} this entry refers to.
     * 
     * @param n The {@link PastryNodeDescriptor} this entry refers to
     */
    Entry setNode(PastryNodeDescriptor n) {
      node = n;
      return this;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String toString() {
      return "node: " + node + ", distance from owner: " + distance;
    }
  }
}